package com.salim.leetcode.$52;

import java.util.*;

public class NQueensII {
    public int result = 0;
    public int length = 0;
    public Set<Integer> leftDiagonals = new HashSet<>();
    public Set<Integer> rightDiagonals = new HashSet<>();
    public int totalNQueens(int n) {
        if(n==0){
            return result;
        }
        length = n;
        loop(0,new boolean[length]);
        return result;
    }

    public void loop(int level,boolean[] usedJ){
        for(int j=0;j<usedJ.length;j++){
            if(usedJ[j]){
                continue;
            }
            int diag1 = level - j;
            int diag2 = level + j;
            if(leftDiagonals.contains(diag1)){
                continue;
            }
            if(rightDiagonals.contains(diag2)){
                continue;
            }

            level+=1;
            leftDiagonals.add(diag1);
            rightDiagonals.add(diag2);
            usedJ[j] = true;

            if(level==length){
                result+=1;
            }else{
                loop(level,usedJ);
            }
            level-=1;
            usedJ[j] = false;
            leftDiagonals.remove(diag1);
            rightDiagonals.remove(diag2);
        }
    }

}
